def recurrence(n):
    if n < 1:
        print('0')
    else:
        print(f'enter--{n}--')
        recurrence(n - 1)
        print(f'out~~{n}~~')


def recurrence_02(n):
    if n == 5:
        print('*' * n)
    else:
        print('*' * n)
        recurrence_02(n + 1)
        print('*' * n)


def feibo(n):
    if n == 1 or n == 2:
        return 1
    return feibo(n - 1) + feibo(n - 2)


# 递归计算阶乘
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


# 累加
def add(n):
    if n == 1:
        return 1
    return n + add(n - 1)


def fibonacci(n):
    """
    斐波那契数列
    :param n: 第n个数
    :return:
    """
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)


def fibonacci_list(n):
    f_list = []
    for i in range(1, n + 1):
        # print(fibonacci(i))
        f_list.append(fibonacci(i))
    return f_list


def rec_01(n):
    if n < 1:
        return [n]
    return [n] + rec_01(n - 1)


def fibonacci_02(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)


def fibonacci_03(n):
    """ 用循环方式计算斐波那契数 """
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        pre_pre = 1
        pre = 2
        for i in range(3, n):
            ret = pre + pre_pre
            pre_pre = pre
            pre = ret
        return pre


if __name__ == '__main__':
    print('累加:', add(100))
    print('阶乘:', factorial(5))
    print('rec_01:', rec_01(10))
    recurrence(3)
    num = 15
    print(f'第{num}个斐波那契数: '
          , fibonacci(num)
          , fibonacci_02(num)
          , fibonacci_03(num)
          , feibo(num)
          )
    print(f'{num}个数的斐波那契数列:', fibonacci_list(num))
    recurrence_02(1)
